1. Field of the Invention
The present invention generally relates to switching systems for multiplex communications systems and, more particularly, to a switching scheduler which schedules the transmission times of fixed-length packets in a time-slotted switch that has N input ports and N output ports and wherein each of the N input ports has N queues, one queue corresponding to each output port.
2. Description of the Prior Art
There are many applications in the communications and data processing fields that require the scheduling of a system (usually a switch) that has N input resources and N output resources. This gives rise to a scheduling problem in which the resource requests can be represented by an N.times.N matrix. During a time slot, only one request can be granted in any row or column of this request matrix. The scheduler determines which requests are satisfied during successive time slots. The objective of the scheduler is to provide high throughput, i.e., try to maximize the number of requests that are granted, while also providing fair service to the different requests. Further, in order to achieve high-speed switching, the computational requirements of the scheduler must be very small.
A related scheduling problem has been recognized in the prior art. In this related problem formulation, a "traffic matrix" represents the aggregate demand for input/output (I/O) pairs over a period of time slots. In a heavily overloaded situation in which the input queues to the switch have many requests in them, the traffic matrix could be viewed as a tabulation of the queue contents. This type of problem formulation is common in the area of satellite-switched time-division-multiple-access (SS/TDMA) systems as described, for example, by T. Inukai in "An Efficient SS/TDMA Time Slot Assignment Algorithm", IEEE Trans. on Communications, vol. 27, no. 10, pp. 1449-1455, 1979. A class of optimal algorithms have been developed to satisfy a given traffic matrix within C time slots where C is the maximum aggregate demand, from the traffic matrix, on any input or output. See also C. Rose, "Rapid Optimal Scheduling for Time-Multiplex Switches using a Cellular Automaton", IEEE Trans. on Communications, vol. 37, no. 5, pp. 500-509, May 1989. Unfortunately, these algorithms are computationally expensive and thus do not lend themselves to high-speed switch applications, particularly for large N. In fact, to apply optimal scheduling to situations in which N is large, Rose proposed an approach that uses N.sup.2 processors that run algorithms whose computation times vary as O(N). Thus, in high-speed packet switches with a large number of ports, the computation of the optimal schedule can require a prohibitive amount of hardware.